This invention relates to a high-speed digital device for multiplying any binary number by three.
In many computing devices, and particularly in digital multiplier devices, it is often necessary to multiply a given number x by three. One of the more attractive prior art methods of performing multiplications consists in dividing the multiplier term into groups of bits of constant length and in analyzing such groups to determine a multiple of the multiplicand to be used in order to carry out the desired multiplication as a sequence of accumulations. Once this multiple has been determined, means for generating same must of course be provided.
More specifically, let us assume that, in a multiplication XY to be performed, the multiplier Y is divided into several groups of three bits each, beginning with the lowest-order bit, plus one of the bits of the preceding group. For example, if ##EQU1## Groups g1, g2, g3 and g4 are successively analyzed. To each configuration of a group g corresponds a contribution which is a multiple of X to be added to the contributions of the previous groups to finally provide, after group g4 has been processed, the desired product of XY. The following table summarizes the contributions associated with the various configurations of g.
______________________________________ Bit of Multiple of g preceding g X ______________________________________ 000 0 0 000 1 +X 001 0 +X 001 1 +2X 010 0 +2X 010 1 +3X 011 0 +3X 011 1 +4X 100 0 -4X 100 1 -3X 101 0 -3X 101 1 -2X 110 0 -2X 110 1 -X 111 0 -X 111 1 0 ______________________________________
The above method makes it possible to find a compromise between the number of adders required to build the multiplier device and the speed of the latter. However, it will be seen that the speed of the device is dependent, in particular, upon the time required to determine the multiples of X. This is especially troublesome where the device must perform successive multiplications XY, X'Y', X"Y", etc., at a rate which should be as fast as possible and in any event faster than that at which the operands X, Y, X', Y', etc., are received. In such cases, the so-called pipelining technique is sometimes used. That is, as soon as group g1 of Y has been processed, the associated circuits start processing group g1 of Y', thereby initiating the computation of X'Y', then of X"Y", etc., before the computation of XY is completed. It is clear, therefore, that a device capable of generating the multiples of terms X, X',X", etc., as quickly as possible would be quite useful. Multiples such as X, 2X, 4X, that is, multiples belonging to the family 2.sup.N X, can readily be generated from X. All that is required to do so is to shift X N bit positions toward the higher-order positions. However, this does not apply when 3X or one of its multiples is required.
In a prior art device designed to multiply binary numbers by means of analyses of the groups of bits g that comprise the multiplier, 3X is obtained by adding X to 2X in two successive operations. Two basic cycles of operation instead of one are therefore required. Such a process is too slow and does not permit maintaining an operating cycle of constant duration regardless of the configuration of the groups of bits.
Alternatively, 3X can be generated using an additional device. In that case, the additional device should be inexpensive and capable of operating at high speed.
Accordingly, it is an object of the present invention to provide a high-speed device for multiplying any binary number X by three.
Another object of the invention is to implement such a device using a limited number of circuits, thereby reducing the size of the device.
The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings.